The technique of employing a high speed cache memory intermediate a processor and a main memory to hold a dynamic subset of the information in the main memory in order to speed up system operation is well known in the art. Briefly, the cache holds a dynamically variable collection of main memory information fragments selected and updated such that there is a good chance that the fragments will include instructions and/or data required by the processor in upcoming operations. If there is a cache "hit" on a given operation, the information is available to the processor much faster than if main memory had to be accessed to obtain the same information. Consequently, in many high performance data processing systems, the "cache miss ratio" is one of the major limitations on the system execution rate, and it should therefore be kept as low as possible.
The key to obtaining a low cache miss ratio is obviously one of carefully selecting the information to be placed in the cache from main memory at any given instant. There are several techniques for selecting blocks of instructions for transitory residence in the cache, and the more or less linear use of instructions in programming renders these techniques statistically effective. However, the selection of operand information to be resident in cache memory at a given instant has been much less effective and has been generally limited to transferring one or more contiguous blocks including a cache miss address. This approach only slightly lowers the cache miss ratio and is also an ineffective use of cache capacity.
Thus, those skilled in the art will understand that it would be highly desirable to provide means for selecting operand information for transitory storage in a cache memory in such a manner as to significantly lower the cache miss ratio. That end was accomplished in accordance with the invention disclosed and claimed in U.S. Patent Application Ser. No. 07/364,943 filed Jun. 12, 1989, for METHOD AND APPARATUS FOR PREDICTING ADDRESS OF A SUBSEQUENT CACHE REQUEST UPON ANALYZING ADDRESS PATTERNS STORED IN SEPARATE MISS STACK by Charles P. Ryan, now U.S. Pat. No. 5,093,777, by special purpose apparatus in the cache memory which stores recent cache misses and searches for operand patterns therein. Any detected operand pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss.
Inventions which address other improvements to the invention disclosed and claimed in U.S. Pat. No. 5,093,777 are discussed immediately below for their peripheral relevance to the present invention.
Under certain operating conditions, the full time use of the procedure disclosed and claimed in U.S. Pat. No. 5,093,777 can actually raise the long term miss ratio (i.e., lower the long term hit ratio). In a typical cache based processor that executes a single process during a given period, the cache hit ratio will stabilize after some time interval following the institution of the process. If a change to another process is made, new instructions and data must be loaded into the cache such that cache hit ratio instantaneously drops dramatically and then increases as the new process is "experienced". If the cache miss prediction mechanism is in operation, the initial rate of increase in the cache hit ratio is much faster. However, the hit ratio never reaches the level it would reach in the long term if the cache miss prediction mechanism was not in use. This result is caused by the fact that the cache miss prediction mechanism continues to find and load from main memory the next possible miss which, however, is not used, thus forcing the cache to replace blocks that are more important.
The invention disclosed and claimed in U.S. Patent Application Ser. No. 07/841,687 filed Feb. 26, 1992, for SELECTIVELY ENABLED CACHE MISS PREDICTION METHOD AND APPARATUS by Charles P. Ryan overcomes the limiting effect of using the cache miss prediction mechanism continuously after a process has been changed by selectively enabling the cache miss prediction mechanism only during cache "in-rush" following a process change to increase the recovery rate; thereafter, it is disabled, based upon timing-out a timer or reaching a hit ratio threshold, in order that normal procedures allow the hit ratio to stabilize at a higher percentage than if the cache miss prediction mechanism were operated continuously.
There are operating conditions, however, under which it would be advantageous to have the cache miss prediction mechanism in operation even after cache inrush following a process change. An example of such an operating condition is when very large sets (even in excess of the cache size) of regularly addressed operand data (matrix/vector/strings) are used by a procedure. An invention which takes advantage of this characteristic is disclosed in U.S. Patent Application Ser. No. 07/850,713 filed Mar. 13, 1992, for ADAPTIVE CACHE MISS PREDICTION MECHANISM by Charles P. Ryan. This feature is achieved by special purpose apparatus which stores recent cache misses and searches for address patterns therein. Any detected pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss. The cache miss prediction mechanism is adaptively selectively enabled by an adaptive circuit that develops a short term operand cache hit ratio history and responds to ratio improving and ratio deteriorating trends by accordingly enabling and disabling the cache miss prediction mechanism.
The cache miss prediction circuit disclosed therein was best adapted to operate in an environment where the main memory address space is linear and unbroken. However, in many processors, the main memory address space is paged with the sizes of the pages typically falling within the range 1024-4096 bytes. In a paged main memory environment, the memory address developed during normal operation is a virtual address that must be translated from the virtual configuration to a physical configuration. This is typically achieved by dividing the address into two fields. Some lower number of bits, which represent addressing within a page, are not translated. All the remaining, upper bits are translated by a paging unit within the processor from the virtual address space to a physical address space in a manner which is invisible to the running program. The principal purpose of providing a paged main memory is to permit addressing a much larger virtual memory; however, secondary purposes of importance include the facilitation of providing security to selected main memory pages and the ability to continue operation if a page of main memory is faulty.
The method and apparatus disclosed in U.S. Pat. No. 5,093,777 also had the inherent drawback that the patterns are always searched in the same sequence. If, for example, the pattern found is the last of eight searched, it would always require seven search cycles to find the pattern, a fact which adversely affects the advantage of prefetching the next request. This drawback was addressed and overcome by the invention disclosed and claimed in U.S. Patent Application Ser. No. 07/906,618 filed Jun. 30, 1992, for PATTERN SEARCH OPTIMIZER FOR CACHE MISS PREDICTION METHOD AND APPARATUS by Charles P. Ryan. This end is achieved by special purpose apparatus which stores recent cache misses and searches for address patterns therein. Any detected pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss. The efficiency of the apparatus is improved by placing the search order for trying patterns into a register stack and providing logic circuitry by which the most recently found select pattern value is placed on top the stack with the remaining select pattern values pushed down accordingly.
The method and apparatus disclosed in U.S. Pat. No. 5,093,777 has another drawback in that it is subject to making invalid predictions or a prediction that may cause a system problem when a page boundary in main memory is crossed since operation is with physical addresses. For example, a pattern which continues onto the next page of the physical main memory may enter memory space which is reserved to some other user (or even confidential) or process, or the next page may be damaged and not intended for use, or it may contain information which is of no value to have in the cache at the present time. If the prediction process carries across a page boundary into a reserved or damaged area of memory, the processor must handle the resulting invalid states before normal processing can continue, and such remedial action may impose a severe performance penalty. This drawback is addressed and overcome by the invention disclosed and claimed in United States Patent Application Ser. No. 07/921,825 filed Jul. 29, 1992, for CACHE MISS PREDICTION METHOD AND APPARATUS FOR USE WITH PAGED MAIN MEMORY IN A DATA PROCESSING SYSTEM by Charles P. Ryan. This end is achieved by special purpose apparatus which stores recent cache misses and searches for address patterns therein. Any detected pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss. The efficiency of the apparatus operating in an environment incorporating a paged main memory is improved by the addition of logic circuitry which serves to inhibit prefetch if a paged boundary would be encountered.
Those skilled in the art will understand that the several inventions discussed above may be used individually or in various combinations to establish effective operand cache features in diverse systems which may vary in cost, size, speed and the like. For those applications, however, which require the utmost in speed, they each are somewhat limited in that patterns are searched for serially. It is the purpose of the present invention to address and break this inherent speed limitation.